The secure and naive way to virtualize shared memory accesses between threads is to log every access to the memory and replay them in the replication machine. This is particularly inefficient in terms of performance.
There is a need for making the shared memory accesses of multithread programs deterministic in order, for instance, to be able to replicate on a backup machine the application virtualized on a primary machine, by simply re-executing the code of the application programs on the replication machine.
A main use could be in fault tolerant systems. In a fault tolerant system, an application runs on a primary machine and its execution is entirely replicated on a second machine (in order to recover, in case of primary failure). The replication is achieved by recording and replay of events that produce non deterministic results or reexecution of code for replicating events producing deterministic results. One other use of making shared memory access by multithread programs deterministic is debugging of the virtualized programs which is performed by re-executing the code (on the same machine in this case) as many times as necessary.
Interleaved execution of processes with respect to a writable shared memory region is a potential source of non-determinism. In order to be able to make the shared memory accesses deterministic, the order in which the shared memory is accessed by concurrent processes needs to be recorded. In the case of a uniprocessor machine, the recording operation can be optimized by just logging one record per scheduling period. Instead of logging every access to the shared memory region, it is sufficient to log one record per scheduling period in which the shared memory region was accessed, if the record specifies the process identifier along with the location of the first instruction at which the access was made in that scheduling period and the number of user instructions executed by the process until the end of that scheduling period. Consequently, for a scheduling period the shared memory accesses have become deterministic events. To reproduce this event in a backup machine it is sufficient to restore the record of the scheduling period and to reexecute the code for this period.
To extend this optimization to multi-processor machines, the uniprocessor property of mutual exclusion needs to be imposed to serialize accesses to the shared memory regions. The French patent application WO2006/077261 assigned to Internal Business Machines Corporation describes how to implement deterministic replay of multi-process applications on multiprocessor systems. A shared memory access control mechanism is described wherein; it uses the Memory Management Unit of the processor (MMU). Control to access to the shared memory is done by programming the MMU (Memory Management Unit) hardware device of one processor to allow granting access to a memory page, the MMU of other processors being programmed to deny any access to the same page.
In a scheduling period, on multi-processor machines, an exclusive access to the shared memory is given to each individual process. The page tables of the processes are instrumented to selectively grant access to a single process in each scheduling period. However, in case of multi-thread programs, the participating processes share their address space; applying the mono processor solution by instrumenting the shared page table would affect the entire thread group. Further, in contrast to processes in a mono-processor environment, entire address space would be shared among the threads and for monitoring and controlling these accesses, any access to writable portions of the shared address space has to be tracked. This implies that each task can have its own private set of memory descriptors even if the memory pages are shared. This is not the case for multi thread programs where all the memory descriptors are shared. This patent application suggests that for tracking shared memory accesses by one task creating more than one thread, the structure of the page table entries need to be extended to each thread cloned within each task which is monitored as described in the invention. The principle of the invention can be applied to each task or each thread within one task, the accesses to shared memory pages being exclusive over an entire duration of an activation period denied by the scheduler. During this period the shared memory pages are maintained coherent.
There is thus a need for extending the virtual memory manager module of the kernel to make the mechanism of shared memory accesses serialization of the prior art applicable to multi-thread programs which all share their entire memory space (rather than processes sharing only a subset of their memory space).
U.S. Pat. No. 6,854,108 describes a method for deterministically replaying an observable run time behavior of distributed multithreaded programs on multi processors. This method relies on instrumentation of locking routines in a JVM. This solution implies modification of the JVM and is limited to pure Java applications running on top of the JVM and is limited by the fact that all the memory accesses have to be protected by lock to be done by the JVM.
There is a need to provide a shared memory access control applying to multithreaded processes on multi-processor computers which is generic and transparently applicable to any type of applications.